1. Field of the Invention
The present invention relates generally to rendering graphics system, and more particularly to texture mapping in graphics systems.
2. Description of Background Art
In many graphics applications, three-dimensional images are displayed on a computer screen by rendering a large number of graphic primitives, which are typically polygons (such as triangles). Primitives are defined using a number of parameters derived from three-dimensional object models, using transformation algorithms, projections, and light calculations. Initially, these parameters (or “channel values”) are determined for each vertex of the primitive. For each vertex, these channel values include: a vertex location (X, Y); color values (such as R, G, B) or texture coordinates (U,V), depth of the vertex location (Z) blending parameter, such as an alpha value, and the like. Subsequently, the interior of each primitive is rasterized into a frame buffer using texture-mapping or other techniques for assigning color values to points within the primitives. Conventional techniques use some form of interpolation or incremental calculation to determine on a sequential basis the channel values of the points within the interior of each of the primitives that are rendered.
Many techniques are known for rendering graphic primitives in such graphics systems. For example, Foley et al., Computer Graphics: Principles and Practice, 2d. ed., 1990, describes methods for computing edges and for interpolating values for pixels within the primitives. Conventionally, primitive edges are determined from vertex points using line interpolation, and scan lines between the determined edges are filled with linearly or perspective interpolated values for color and other parameters.
Alternatively, techniques such as “Pixel-Planes” may be used to simultaneously determine linear or perspective functions for pixels within the frame buffer. Parallel linear expression evaluators comprising a binary tree of multiply-accumulator nodes are used to evaluate the expressions. See, for example, Fuchs et al., “Pixel-Planes 5: A Heterogeneous Multiprocessor Graphics System Using Processor-Enhanced Memories,” in Computer Graphics, vol. 23, no. 3, July 1989. This technique has the advantage of improved parallelism, but requires expensive dedicated logic for each pixel.
Another technique, described in Pineda, “A Parallel Algorithm for Polygon Rasterization,” in Computer Graphics, vol. 22, no. 4, August 1988, uses an edge function. An edge function is a linear function that subdivides a two-dimensional plane into three regions: points on the line, points to the “left” of the line, and points to the “right” of the line. Boolean combinations of edge functions are used to define primitives; for example, three edge functions can be combined to define a triangle primitive.
Once the edges are defined, traversal is employed to fill in the values for points within the primitive. Traversal is most often accomplished by sequentially scanning rows within the graphic primitive, and using linear interpolation to determine a value at each point on each row. See, for example, Foley et al., Computer Graphics: Principles and Practice, 2d. ed., 1990, pp. 870-71. Also, see Schilling, “A New Simple and Efficient Antialiasing with Subpixel Masks”, in Computer Graphics, vol. 25, no. 4, July 1991, for antialiasing approach employing edge functions to determine distances from relevant edges.
In conventional scan conversion, processing is divided into two stages, namely a setup stage and a rasterization stage. The setup stage receives individual primitives that are defined by the relevant values at their vertices. The setup stage computes parameters that are needed for performing interpolation on an incremental or point-by-point basis. This computation can be an expensive process. In the rasterization stage, primitives are traversed to determine values at each individual pixel point.
Conventional graphics system thus encounter a tradeoff in computational load between the setup stage and the rasterization stage. The use of larger primitives shifts much of the load to the rasterization stage, as fewer primitives are used but each requires greater amounts of interpolation. Conversely, the use of smaller primitives reduces the amount of interpolation, but necessarily involves more computational load in the setup stage due to the increased number of primitives. Conventional graphics systems use distinct processor modules for the two stages, so that computational capacity cannot easily be shifted from one stage to the other. Therefore, such systems are often unable to efficiently process graphics when the number and size of primitives change. In other words, such conventional systems may be optimized for greater computational load in one or the other of the stages, but may not easily handle shifting loads as may occur in dynamic graphic images.
Another disadvantage of conventional systems is that the rasterization stage requires sequential traversal of scan lines within the primitives. In some applications, where a value for a given pixel location within a primitive may be needed, it may be inefficient to perform lengthy traversal operations of large portions of the primitive in order to determine the desired value.
What is needed is a system that combines the setup and rasterization stages in such a way that computational load can easily be shifted from one to the other without adversely affecting overall performance. What is further needed is a system for efficiently interpolating values within graphic primitives without extensive traversal of primitives, and also while avoiding the problems and inefficiencies of prior art schemes.